package main

import "fmt"

//递归超出时间限制
func fib1(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	return fib1(n-1) + fib1(n-2)
}

//0ms 100%,1.8MB 55%
func fib(n int) int {
	var c int = 1e9 + 7
	dp := []int{0, 1}
	for i := 2; i <= n; i++ {
		dp = append(dp, (dp[i-1]%c+dp[i-2]%c)%c)
	}
	return dp[n] % c
}

func main() {
	fmt.Println(fib1(3))
	fmt.Println(fib(95))
}
